package com.wfm.leetcode.editor.cn;
public class P剑指OfferII105岛屿的最大面积{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int max = 0;
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(grid[i][j]==1&&!visited[i][j]){
                    int dfs = dfs(grid, m, n, visited, i, j);
                    max = Math.max(max,dfs);
                }
            }
        }
        return max;
    }
    int dfs(int[][] grid,int m,int n, boolean[][] visited ,int i,int j){
        if(i<0||i>=m||j<0||j>=n){
            return 0;
        }
        if(visited[i][j]){
            return 0;
        }
        if(grid[i][j]!=1){
            return 0;
        }
        visited[i][j]=true;
        return 1+dfs(grid,m,n,visited,i-1,j)+
                dfs(grid,m,n,visited,i+1,j)+
                dfs(grid,m,n,visited,i,j-1)+
                dfs(grid,m,n,visited,i,j+1);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new P剑指OfferII105岛屿的最大面积().new Solution();
        int[][] grid = new int[][]{
                {0,0,1,0,0,0,0,1,0,0,0,0,0},
                {0,0,0,0,0,0,0,1,1,1,0,0,0},
                {0,1,1,0,1,0,0,0,0,0,0,0,0},
                {0,1,0,0,1,1,0,0,1,0,1,0,0},
                {0,1,0,0,1,1,0,0,1,1,1,0,0},
                {0,0,0,0,0,0,0,0,0,0,1,0,0},
                {0,0,0,0,0,0,0,1,1,1,0,0,0},
                {0,0,0,0,0,0,0,1,1,0,0,0,0}
        };
        int i = solution.maxAreaOfIsland(grid);
        System.out.println(i);
    }
}